/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package dungeonsolver.controller.algorithm;

import dungeonsolver.helper.Utility;
import dungeonsolver.model.Labyrinth;
import java.awt.Point;
import java.util.Vector;
/**
 *
 * @author HP
 */
public class AlgorithmUCS implements IAlgorithm
{
    Labyrinth labyrinth;

    public Point[] getPath(Labyrinth labyrinth, Point from, Point to) {
        //System.out.println(to);
        //Check
        if (labyrinth == null || from.equals(to)) return new Point[0];

        //Create visited map
        boolean[][] Map = labyrinth.getVisitMap();

        //Create variables
        this.labyrinth = labyrinth;
        Vector<Point> Path	= new Vector<Point>();
        Point   current = (Point)from.clone();

        //Initialize prevMap
        Point[][] prevMap = createPrevMap();

        //Initialize cost map
        int[][] costMap = createCostMap();
        costMap[current.x][current.y] = 0;
        
        int steps = 0;
        boolean found = true;
        while (found) {
            String log = "Currently at point ["+current.x+" , " +current.y+"] with cost = " + costMap[current.x][current.y];
            Utility.instance().addLog(log);
            log = "";

            Map[current.x][current.y] = true;
            //Path.add((Point) current.clone());

            //Expands
            int currentCost = costMap[current.x][current.y];
            Point[] neighbors = labyrinth.getNeighbors(current);
            for (int i = 0 ; i < neighbors.length ; i++) {
                Point now = neighbors[i];

                if (!Map[now.x][now.y]) {
                    if (currentCost + 1 < costMap[now.x][now.y] || costMap[now.x][now.y] == -1) {
                        log = "    Expanding to ["+now.x+" , " +now.y+"] with cost   = " + (currentCost + 1);
                        costMap[now.x][now.y] = currentCost + 1;
                        prevMap[now.x][now.y] = (Point)current.clone();
                        Utility.instance().addLog(log);
                    }
                }
            }

            //Check next steps
            Point candidateCurrent = new Point(0,0);
            int min = 1000000000;
            found = false;
            for (int x = 0 ; x < labyrinth.getWidth() ; x++) {
                for (int y = 0 ; y < labyrinth.getHeight() ; y++) {
                    if (!Map[x][y] && costMap[x][y] != -1 && costMap[x][y] < min) {
                        min = costMap[x][y];
                        candidateCurrent = new Point(x,y);
                        found = true;
                    }
                }
            }
            log = "\n";
            Utility.instance().addLog(log);

            current = candidateCurrent;
            steps++;
        }

        String log = "Path finding done, calculated cost is " + costMap[to.x][to.y];
        Utility.instance().addLog(log);
        //System.out.println(prevMap[labyrinth.getExit().x][labyrinth.getExit().y].toString());
        //Generate path
        //System.out.println("======================================");
        current = (Point)to.clone();
        Path.insertElementAt((Point) current.clone(), 0);
        while (prevMap[current.x][current.y].x != -1) {
            //System.out.println(current);
            current = prevMap[current.x][current.y];
            if (prevMap[current.x][current.y].x != -1)
                Path.insertElementAt((Point) current.clone(), 0);
        }

        Point[] path = new Point[Path.size()];
        for (int i = 0; i < path.length; i++) path[i] = Path.elementAt(i);
        return path;
    }

    private int[][] createCostMap() {
        int[][] retval = new int[labyrinth.getWidth()][labyrinth.getHeight()];

        for (int x = 0 ; x < labyrinth.getWidth() ; x++) {
            for (int y = 0 ; y < labyrinth.getHeight() ; y++) {
                retval[x][y] = -1;
            }
        }
        
        return retval;
    }

    private Point[][] createPrevMap() {
        Point[][] retval = new Point[labyrinth.getWidth()][labyrinth.getHeight()];

        for (int x = 0 ; x < labyrinth.getWidth() ; x++) {
            for (int y = 0 ; y < labyrinth.getHeight() ; y++) {
                retval[x][y] = new Point(-1,-1);
            }
        }

        return retval;
    }

}
